> >and
use that to construct the DFA for the complement: > 
“You can always get closure from yourself.” - Nick Viall
By definition, the union of two regular languages is regular, the concatenation of two regular languages is regular, and the star of a regular language is regular. In this section we look at other operations on regular languages that are guaranteed to produce regular languages. Specifically:
Theorems of this kind are called closure properties, because they tell us that the collection of all regular languages is closed under particular operations. (A set is closed under an operation if applying that operation to members of the set is guaranteed to produce members of that same set.)
Theorem
The complement of a regular language is regular. > Proof: > >Let \(S\) be an arbitrary regular language. There exists a DFA \(D\) such that \(S = L(D)\). Define \(D'\) to be a DFA just like \(D\) but with accept/reject swapped (i.e., the set \(F\) of final/accepting states is replaced by \(Q \setminus F\)). Then \(D'\) accepts a string iff \(D\) rejects that string. That is, \(L(D') = L(D)^C = S^C\), so the complement \(S^C\) of \(S\) is regular too.
Example
The complement of the set \(\{\ ab^nc\ |\
n\geq 0\ \}\) is regular, because we can find a DFA for this set:
> > > >and
use that to construct the DFA for the complement: >
Theorem
The intersection of two regular languages is regular. >
Proof 1:
Let \(L_1\) and \(L_2\) be arbitrary regular languages. Since
\((L_1\cap L_2)^c= L_1^c\cup L_2^c\) (a
form of DeMorgan’s Law), it follows that \(L_1\cap L_2 = (L_1^c\cup L_2^c)^c\). We
know \(L_1^c\) and \(L_2^c\) are regular. So \(L_1^c\cup L_2^c\) is regular Thus \(L_1\cap L_2 = (L_1^c∪ L_2^cc)^c\) is
regular.
Theorem
The intersection of two regular languages is regular. >
Proof 2:
Given DFAs \(D_1=(Q_1,\Sigma, \delta_1,
q_{01}, F_1)\) and \(D_2=(Q_2,\Sigma,
\delta_2, q_{02}, F_2)\) accepting the two regular languages, we
can construct a new DFA \(D=(Q,\Sigma,\delta,q_0,F)\), called the
Product Automaton of \(D_1\)
and \(D_2\) that accepts inputs and
keeps track of what states \(D_1\)
and \(D_2\) would be in when
given those inputs (i.e., we are simulating the two machines being run
in parallel), and only accept if both machines would accept the input
string. > >Formally, we can define the components of the product
automaton as follows: > >- \(Q :=
Q_1\times Q_2\)
> The states of \(D\) are pairs
telling us where \(D_1\) and \(D_2\) would > be on the input so far.
>- \(q_0 := \langle q_{01}, q_{02}
\rangle\)
> When we start, both machines are in their start states >- \(\delta(\langle q_1,q_2 \rangle, a) :=
\langle\delta_1(q_1,a), \delta_2(q_2,a)\rangle\)
> If the first machine is in state \(q_1\) and the second machine is in state
\(q_2\) and we see input \(a\), we use the transition functions of the
machines to figure out which states the two machines will be in
afterwards. >- \(F := F_1 \times
F_2\)
> We have found a string in the intersection iff both machines have
reached an accepting state.
Example
Here are two small DFAs and their product automaton: > 
> >— > > 
> >
>Initially the first DFA is in state A and the second DFA is in state
L. If the first input is a, then the first DFA switches to
state X and the second machine switches to state K. Conversely, if the
first input is b, then the first DFA stays in state A, but
the second DFA switches to state K. And so on…
Previous: 6.5 Kleene’s Theorem
Next: 6.7 Regular Expressions